// run: time $exec < input
#include <iostream>
#include <cstring>

long long const maxn = 1007;
long long const maxm = 2007;
long long f[maxm];
long long g[maxm];
long long a[maxn], b[maxn], w[maxn];
long long n, m;

int main()
{
	std::ios::sync_with_stdio(false);
	long long T; std::cin >> T;
	while (T--) {
		std::cin >> m >> n;
		for (long long i = 0; i < n; i++)
			std::cin >> w[i] >> a[i] >> b[i];

		std::memset(f, 0, sizeof(f));
		std::memset(g, 0, sizeof(g));
		for (long long i = 0; i < n; i++) {
			for (long long j = 0; j <= m; j++) {
				if (j >= w[i]) {
					if (f[j - w[i]] + a[i] + b[i] >= f[j]) {
						f[j] = f[j - w[i]] + a[i];
						g[j] = 1;
					} else
						g[j] = 0;
				} else {
					g[j] = 0;
				}
			}
			for (long long j = 0; j <= m; j++)
				if (g[j]) f[j] += b[i];
		}
		std::cout << f[m] << '\n';
	}
}

